class MergeSort {
private:
    vector<int> data;

public:
    void sort(vector<int>& data) {
        this->data = std::move(data);
        dfs(0, this->data.size() - 1);
        data = std::move(this->data);
    }

private:
    void dfs(int start, int end) {
        if (start == end) {
            return;
        }

        int mid = (start + end) / 2;

        dfs(start, mid);
        dfs(mid + 1, end);
        merge(start, mid, end);
    }

    void merge(int start, int mid, int end) {
        int i = start, j = mid + 1;
        vector<int> temp;
        while (i <= mid && j <= end) {
            if (data[i] < data[j]) {
                temp.push_back(data[i++]);
            } else {
                temp.push_back(data[j++]);
            }
        }
        while (i <= mid) {
            temp.push_back(data[i++]);
        }
        while (j <= end) {
            temp.push_back(data[j++]);
        }
        for (int k = start, t = 0; k <= end; k++, t++) {
            data[k] = temp[t];
        }
    }
};